package stack;

import java.util.*;

/**
 * @author dx
 * @version 1.0
 * @date 2022/3/28 17:09
 * @description: nums1中数字x的下一个更大元素是指z在nums2中对应位置右侧的第一个比x大的元素
 */
public class NextGreaterNum {

    public static void main(String []args){
        int []test1 = {4,1,2};
        int []test2 = {1,3,4,2};
       int []result = new int[3];
        result = nextGreaterElement2(test1,test2);
        for(int num: result){
            System.out.println(num);
        }
    }
   //方法1
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {

        int len1 = nums1.length;
        int len2 = nums2.length;
        List<Integer> list = new ArrayList<Integer>();
        int []result = new int[len1];

        //将数组2的元素添加到ArrayList中去 共len2个
        for(int i =0;i<len2;i++){
            list.add(nums2[i]);
        }
        for(int i=0;i<len1;i++){   //遍历数组1
            int obj = list.indexOf(nums1[i]);//数组2中出现该元素的索引值
            int tmp = 0;
            while(obj<len2){
                obj++;
                if(obj == len2){
                    result[i] = -1;
                    break;
                }
                tmp = list.get(obj);
                if(tmp>nums1[i]){
                    result[i] = tmp;
                    break;
                }
            }
        }
        return result;
    }
    //方法2：通过栈 记录每个元素最右边第一个比自己大的元素，然后通过HashMap记录下来
    public static int[] nextGreaterElement2(int[] nums1, int[] nums2){
        // ArrayDeque 基于数组实现双端队列，
        // 而 LinkedList 基于双向链表实现双端队列，数组采用连续的内存地址空间，通过下标索引访问，
        // 链表是非连续的内存地址空间，通过指针访问，所以在寻址方面数组的效率高于链表。
        Deque<Integer> stack = new ArrayDeque<Integer>();
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();

        for(int i=nums2.length-1;i>=0;--i){
            while (!stack.isEmpty() && nums2[i]>=stack.peek()){
                stack.pop();
            }
            map.put(nums2[i],stack.isEmpty()? -1:stack.peek());  //考虑到最后一个元素一定在右边没有一个最大值
            stack.push(nums2[i]);   //把当前的值存到栈顶,保证下一个元素找最近比自己大的元素
        }
        int [] res = new int[nums1.length];
        for(int i = 0;i<nums1.length;i++){
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}
